package com.lw.leetcode.str.b;

/**
 * 1081. 不同字符的最小子序列
 * 316. 去除重复字母
 *
 * @Author liw
 * @Date 2021/5/17 9:43
 * @Version 1.0
 */
public class SmallestSubsequence {

    public static void main(String[] args) {
        SmallestSubsequence test = new SmallestSubsequence();
        String s = test.smallestSubsequence("cbacdcbc");
        System.out.println(s);
    }

    public String smallestSubsequence(String s) {
        int length = s.length();
        if (length == 1) {
            return s;
        }
        int[] count = new int[26];
        for (int i = 0; i < length; i++) {
            count[(s.charAt(i) - 'a')] += 1;
        }
        boolean[] flag = new boolean[26];
        StringBuilder sb = new StringBuilder(length);
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            int index = c - 'a';
            if (!flag[index]) {
                while (sb.length() > 0) {
                    char last = sb.charAt(sb.length() - 1);
                    if (last > c && count[last - 'a'] > 0) {
                        sb.deleteCharAt(sb.length() - 1);
                        flag[last - 'a'] = false;
                    } else {
                        break;
                    }
                }
                sb.append(c);
                flag[index] = true;
            }
            count[index] -= 1;
        }
        return sb.toString();
    }
}
